home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000045_swampler@noao.edu _Wed Dec 28 13:33:14 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  4KB
  1. Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 28 Dec 1994 13:33:44 MST
  2. Received: from noao.edu by optima.CS.Arizona.EDU (5.65c/15) via SMTP
  3.     id AA27716; Wed, 28 Dec 1994 13:33:43 MST
  4. Received: from orpheus.gemini.edu by noao.edu (4.1/SAG-Noao.G96)
  5.     id AA16684; Wed, 28 Dec 94 13:33:42 MST; for icon-group@cs.arizona.edu
  6. Received: by orpheus.gemini.edu (5.0/SMI-SVR4-SAG03X)
  7.     id AA15462; Wed, 28 Dec 1994 13:33:16 +0700
  8. Message-Id: <9412282033.AA15462@orpheus.gemini.edu>
  9. From: swampler@noao.edu
  10. Date: Wed, 28 Dec 1994 13:33:14 GMT+447
  11. X-Mailer: Mail User's Shell (7.2.3 5/22/91)
  12. To: icon-group@cs.arizona.edu
  13. Subject: Re: Truth Tables...
  14. Content-Length: 2952
  15.  
  16. I think I understand more of what the original problem was (maybe someone
  17.   could mail to me again)?  I like Jerry Nowlin's solution.  Here's a version
  18.   of it, recast to use strings instead of lists (because I like strings
  19.   more than lists - must be my SNOBOL4 background raising its head again).
  20.  
  21.   I think it differs from Jerry's solution in the definition of XOR on
  22.   more than 2 values.  See the comment in my code on this point.  I am
  23.   curious as to how logicians define it.
  24.  
  25.   -------
  26.       procedure main(args)
  27.          local n, t
  28.       
  29.          n := integer(args[1]) | 2
  30.       
  31.          every t := gen_truths(n) do {
  32.             every writes(format( !t |                  # values
  33.                                  "|" |              # separator
  34.                                  s_and(t) | s_or(t) | s_xor(t)  # functions
  35.                                ))
  36.             write()
  37.             }
  38.       
  39.       end
  40.       
  41.       procedure format(s)
  42.          return center(s, 5)
  43.       end
  44.       
  45.       # Generate all permutations of a n-wide boolean variable set
  46.       procedure gen_truths(n)
  47.          if n > 0 then suspend ("F"|"T") || gen_truths(n-1)
  48.                   else return ""
  49.       end
  50.       
  51.       # AND of an arbitrary number of values
  52.       procedure s_and(t)
  53.          return if upto('F',t) then "F" else "T"
  54.       end
  55.       
  56.       # OR of an arbitrary number of values
  57.       procedure s_or(t)
  58.          return if upto('T',t) then "T" else "F"
  59.       end
  60.       
  61.       # XOR of an arbitrary number of values
  62.       #
  63.       # This raises an interesting point, just *what is* the definition
  64.       #   of 'xor' with more than 2 arguments?  This solution assumes
  65.       #   definition is 'exactly one TRUE', which is different than
  66.       #   an answer build up through iterative (or recursive) applications
  67.       #   of xor on two values at a time.  I chose this definition
  68.       #   because with the other, xor isn't associative.  Consider:
  69.       #
  70.       #   Case 1: XOR(v1,v2,v3) <- (v1 xor v2) xor v3
  71.       #   Case 2: XOR(v1,v2,v3) <- v1 xor (v2 xor v3)
  72.       #   Case 3: XOR(v1,v2,v3) <- s_xor(v1||v2||v3)    {used here}
  73.       #
  74.       #   with the call XOR(T,F,F)
  75.       #
  76.       #      Case 1: produces T
  77.       #      Case 2: produces F
  78.       #      Case 3: produces T
  79.       #
  80.       #   Cases 1 and 2 become stranger as the number of arguments increase.
  81.       #   One can produce a solution using Case 3 to mimic either Case 1 or
  82.       #   Case 2, anyway, e.g:
  83.       #
  84.       #       s_xor(s_xor(v1||v2)||v3)
  85.       #
  86.       #   What do real mathematicians use?   What happens in 'J'?
  87.       #
  88.       procedure s_xor(t)
  89.          return if i := upto('T',t) then {
  90.                    if upto('T',t,i+1) then "F" else "T"
  91.                    }
  92.                 else "F"
  93.       end
  94.  
  95. -- 
  96. Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)]
  97. --
  98. The Gods that were smiling when you were born are laughing now.
  99.                       -- found in a fortune cookie